#include <cstdio>
#include <algorithm>

#define V 32001 
#define N 62

using namespace std; 

typedef long long ll; 

int v[N]; 	//price
int w[N]; 	//priority
int r[N]; 	//relation

int n, m; 


int k[V]; 
int a[V]; 	// index is price, 
				// value is maximum product that can be bought in 

int main()
{
	int i, j; 
	ll  ms; 
	
	ll  last_k=0; 
	int last_a=0; 

	freopen("p1064_3.in", "r", stdin); 
	
	scanf("%d %d", &m, &n); 
	for (i=1; i<=n; i++) {
		scanf("%d %d %d", &v[i], &w[i], &r[i]); 
		w[i] = w[i]*v[i]; 
		printf("input: i=%d, v=%d, w=%d, r=%d\n", i, v[i], w[i], r[i]); 
	}

	for (i=1; i<=n; i++) {
		if (r[i]!=0)
			continue; 
		printf("\n"); 
		for (j=m; j>=v[i]; j--) { 
			if (a[j-v[i]]+w[i]>a[j]) {
				a[j] = a[j-v[i]]+w[i]; 
				k[j] = k[j-v[i]] | (1ll<<i); 
			}
			if (last_k!=k[j] || last_a!=a[j]) {
				printf("%d, %d: a[j]=%I64d, %I64x\n", i, j, a[j], k[j]); 
				last_k=k[j]; 
				last_a=a[j]; 
			}
		}
	}

	for (i=1; i<=n; i++) {
		if (r[i]==0)
			continue; 
		ms = (1ll<<r[i]); 
		for (j=m; j>=v[i]; j--) { 
			if ((k[j-v[i]]&ms)!=0) {
				if (a[j-v[i]]+w[i]>a[j]) {
					if (last_a!=a[j] && last_k!=a[j-v[i]]+w[i]) {
						printf("here, j=%d, a=%d, b=%d\n", j, a[j], a[j-v[i]]+w[i]); 
						last_a = a[j]; 
						last_k = a[j-v[i]]+w[i]; 
					}
					a[j] = a[j-v[i]]+w[i]; 
					k[j] = k[j-v[i]] | (1ll&i); 
				}
			}
		}
	}

	printf("%d\n", a[m]); 
	return 0; 
}


